package com.leetcode.算法策略相关.动态规划;

/**
 * @author: ZhouBert
 * @date: 2021/3/8
 * @description: 132. 分割回文串 II
 * https://leetcode-cn.com/problems/palindrome-partitioning-ii/
 * 【回文串的结果可以存储，使用 DP 完成预处理！】
 */
public class C_132_分割回文串II {

static C_132_分割回文串II action = new C_132_分割回文串II();

	public static void main(String[] args) {
//test1();
//test2();
//test3();
//		test4();
		test5();
	}

	public static void test1() {
		// 1
		String s = "aab";
		int res = action.minCut(s);
		System.out.println("res = " + res);
	}


	public static void test2() {
		// 0
		String s = "a";
		int res = action.minCut(s);
		System.out.println("res = " + res);
	}

	public static void test3() {
		// 1
		String s = "ab";
		int res = action.minCut(s);
		System.out.println("res = " + res);
	}

	public static void test4() {
		// 1
		String s = "aaabaa";
		int res = action.minCut(s);
		System.out.println("res = " + res);
	}



	public static void test5() {
		// 1
		String s = "adabdcaebdcebdcacaaaadbbcadabcbeabaadcbcaaddebdbddcbdacdbbaedbdaaecabdceddccbdeeddccdaabbabbdedaaabcdadbdabeacbeadbaddcbaacdbabcccbaceedbcccedbeecbccaecadccbdbdccbcbaacccbddcccbaedbacdbcaccdcaadcbaebebcceabbdcdeaabdbabadeaaaaedbdbcebcbddebccacacddebecabccbbdcbecbaeedcdacdcbdbebbacddddaabaedabbaaabaddcdaadcccdeebcabacdadbaacdccbeceddeebbbdbaaaaabaeecccaebdeabddacbedededebdebabdbcbdcbadbeeceecdcdbbdcbdbeeebcdcabdeeacabdeaedebbcaacdadaecbccbededceceabdcabdeabbcdecdedadcaebaababeedcaacdbdacbccdbcece";
		int res = action.minCut(s);
		System.out.println("res = " + res);
	}




	/**
	 * 暴力贪心
	 * 如果从一个方向上，这个思路是有缺陷的。
	 * 改为从两个方向上进行判断
	 * 但是 test5 过不了！
	 * 看来还是思路有问题，不能用贪心！
	 *
	 * @param s
	 * @return
	 */
	public int minCut(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
//		if (s.equals("adabdcaebdcebdcacaaaadbbcadabcbeabaadcbcaaddebdbddcbdacdbbaedbdaaecabdceddccbdeeddccdaabbabbdedaaabcdadbdabeacbeadbaddcbaacdbabcccbaceedbcccedbeecbccaecadccbdbdccbcbaacccbddcccbaedbacdbcaccdcaadcbaebebcceabbdcdeaabdbabadeaaaaedbdbcebcbddebccacacddebecabccbbdcbecbaeedcdacdcbdbebbacddddaabaedabbaaabaddcdaadcccdeebcabacdadbaacdccbeceddeebbbdbaaaaabaeecccaebdeabddacbedededebdebabdbcbdcbadbeeceecdcdbbdcbdbeeebcdcabdeeacabdeaedebbcaacdadaecbccbededceceabdcabdeabbcdecdedadcaebaababeedcaacdbdacbccdbcece")){
//			return 273;
//		}
		int res = minCutByOneWay(chars, len);
		char[] reversChars = new char[len];
		int endIndex=len-1;
		for (int i = 0; i < len; i++) {
			reversChars[endIndex-i]=chars[i];
		}
		res = Math.min(res, minCutByOneWay(reversChars, len));
		return res;
	}

	private int minCutByOneWay(char[] chars, int len){
		int count = -1;
		for (int i = 0; i < len; ) {
			//最少分割
			int last = i + 1;
			for (int j = i + 2; j <= len; j++) {
				if (check(chars, i, j)) {
					last = j;
				}
			}
			i = last;
			count++;
		}
		return count;
	}

	private boolean check(char[] chars, int lastIndex, int index) {
		if (lastIndex == index - 1) {
			return true;
		}
		while (lastIndex<index){
			if (chars[lastIndex++] != chars[--index]){
				return false;
			}
		}
		return true;
	}


}
